package leetcode.pre50;

import java.util.Stack;

/**
 * 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "(()"
 * 输出: 2
 * 解释: 最长有效括号子串为 "()"
 * 示例 2:
 * <p>
 * 输入: ")()())"
 * 输出: 4
 * 解释: 最长有效括号子串为 "()()"
 * <p>
 * 其他括号问题见
 * {@link leetcode.a_总结分布.Code03_括号问题}
 *
 * @date 2020/3/29 16:08
 */
public class Code32_最长有效括号 {
    /**
     * 方式1：暴力统计。对每个子串进行统计。
     * 时间O(n³)
     */
    public static int longestValidParentheses1(String s) {
        if (s == null || s.length() == 0) return 0;
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            //如果当前位置开始到结束，就算都有效也不如res大，直接返回即可
            if (s.length() - i <= res) return res;

            //只有开头是(才有资格去判断
            if (s.charAt(i) == '(') {
                //从i,i+1开始匹配，每次增加两个。
                for (int j = i + 1; j < s.length(); j += 2) {
                    if (isValid(s.substring(i, j + 1))) {
                        res = Math.max(res, j - i + 1);
                    }
                }
            }


        }
        return res;
    }

    private static boolean isValid(String s) {
        if (s == null || s.length() == 0 || (s.length() & 1) != 0) return false;
        int balance = 0;
        for (int i = 0; i < s.length(); i++) {
            balance = s.charAt(i) == '(' ? balance + 1 : balance - 1;
            if (balance < 0) return false;
        }
        return balance == 0;
    }

    /**
     * 错误示范。
     * 遇见(入栈，遇见)出栈。统计最内层匹配的有效长度。
     * 如：((()))
     * 入栈0,1,2,
     * 出栈3，统计3与2匹配。长度2
     * 出栈4，统计4与1匹配。长度4
     * 出栈5，统计5与0匹配。长度6
     * 该方法BUG：
     * ()(())
     * 入栈0，出栈1。统计res=2.
     * 后面入栈2，3，出站4，5 统计了res=4.
     * 把前后分隔了。
     * <p>
     * 弥补思路：
     * 一开始我们入栈-1，目的是让正常连续的n对()不平衡。
     * ()()()().....,栈底始终有-1，标记着本次匹配的效起始点是0位置。
     * <p>
     * 对于()))((()... 第二个(导致无效的，此时栈为空。那么我们标记当前位置2为
     * 下一次可能的有效位置。如果后面仍有)，那么出栈。一旦遇见栈为空，就把当前)入栈。
     * <p>
     * 也就是说对于正常组合的()，我们保证栈一定不为空。
     * 当)多余(，那么栈就会为空，此时将当前)位置入栈。
     * <p>
     * 目的就是对于连续有效的()组合，我们保证栈不空。
     * 对于中间导致前面()组合不能和后面连起来的，我们重新在破坏点统计。
     * <p>
     * 时空都是O(N)
     */
    public static int longestValidParentheses2(String s) {
        if (s == null || s.length() == 0) return 0;
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {//stack pop一个(与当前的)对应,并统计当前有效括号的最大长度
                Integer pop = stack.pop();
                res = Math.max(res, i - pop + 1);
            }
        }
        return res;
    }

    public static int longestValidParentheses3(String s) {
       if(s == null || s.length() <= 1)return 0;
       Stack<Integer> stack = new Stack<>();
       //init index
       stack.push(-1);
       int res = 0;
       // ( ) ) )  (())
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '('){
                stack.push(i);
            }else {
                stack.pop();
                //第二个)后，stack空了，代表不能连续了，无效
                //然后把当前 位置记录 ，表示重新开始记录
                if(stack.isEmpty()){
                    stack.push(i);
                }else {
                // () stack.pop后，stack中还有-1， 1 - (-1) = 2
                    res = Math.max(res,i - stack.peek());
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(longestValidParentheses3("()(())"));
    }
}
